package problem216_Combination_Sum_III;

import java.util.LinkedList;
import java.util.List;

public class Solution {
	public static void main(String[] args){
		System.out.println(new Solution().combinationSum3(3, 9));
	}
	
	public List<List<Integer>> combinationSum3(int k, int n) {
		List<List<Integer>> result=new LinkedList<>();
		List<Integer> curr=new LinkedList<>();
		dfs(curr,result,k,0,n);
		return result;
	}
	
	private void dfs(List<Integer> curr,List<List<Integer>> result,int k,int lastUsed,int target){
		if(target<0||curr.size()>k){
			return;
		}
		if(curr.size()==k&&target==0){
			result.add(new LinkedList<>(curr));
			return;
		}
		for(int i=lastUsed+1;i<=9;i++){
			curr.add(i);
			dfs(curr,result,k,i,target-i);
			curr.remove(curr.size()-1);
		}
	}
}
